package com.sxu.fighting.day1;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * 380
 */
class RandomizedSet {
    int[] arr = new int[200001];
    Random random = new Random();
    Map<Integer,Integer> map = new HashMap<>();
    int idx = -1;

    public RandomizedSet() {
    }

    public boolean insert(int val) {
        if(map.containsKey(val))
            return false;
        arr[++idx] = val;
        map.put(val,idx);
        return true;
    }

    public boolean remove(int val) {
        if(! map.containsKey(val))
            return false;
        int index = map.remove(val);
        if(index != idx){
            map.put(arr[idx],index);
        }
        arr[index] = arr[idx--];
        return true;
    }

    public int getRandom() {
        return arr[random.nextInt(idx + 1)];
    }
}
